目录

一，标准数独（规则数独）

1，规则

2，隐含规则

3，对称性

4，斜线数独

二，标准数独校验、求解

力扣 36. 有效的数独

POJ 3074 Sudoku

POJ 2676 Sudoku

HDU 1426 Sudoku Killer

力扣 37. 解数独

CSU 内部题 数独游戏（2017年院赛F题）

三，湖南省首届高校联合数独大赛

四，常用方法

1，摒除法

（1）摒除法

（2）宫内区块对行列摒除

（3）行列区块对宫摒除

（4）数对摒除

（5）三数组摒除

（6）显性数对

（7）数对占位

（8）显性三数组

（9）三元数组占位

（10）四数组摒除

（11）显性四数组

2，鱼结构

（1）X-Wing

（2）剑鱼

（3）水母

（4）多宝鱼

（5）空矩形

（6）2-String Kite

（7）摩天楼

3，外鳍

（1）外鳍 X-Wing

（2）外鳍剑鱼

（3）外鳍水母

（4）外鳍弗兰肯鱼

（5）外鳍退化 X-Wing

（6）外鳍退化剑鱼

（7）外鳍退化水母

4，唯一矩形

（1）可避免唯一矩形1型

（2）唯一矩形摒除

（3）唯一矩形2型

（4）唯一矩形4型

（5）唯一矩形6型

（6）唯一矩形1型

（7）可避免唯一矩形2型

（8）唯一矩形3型

（9）唯一矩形5型

5，else

（1）SDC

（2）W-Wing

（3）BUG+1

（4）XY-Wing

（5）XYZ-Wing

（6）ALS-XY-Wing

（7）X链

（8）ALS链

（9）远程数对

（10）XY链

（11）ALS-XZ链

数独盘面是个九宫，每一宫又分为九个小格。（宫即3*3的正方形）

在这八十一格中给出一定的已知数字，利用逻辑和推理，在其他的空格上填入1-9的数字。

使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

标准数独有一个隐含的规则，就是根据所给的数字，必须有且只有一个解。

在这个前提下，可以证明，至少需要给出17个数字。

17个数字的数独也不难设计出来，下面的题目中就有。

规则数独，对称性自然只能指数字的位置分布了。

规则数独和不规则数独在数字的分布上其实差别不大，也是那几种对称性，后面给出了一个示例。

相对而言，规则数独要想给出对称的位置分布的初始局面，比较简单。

而且因为格子画的本身就很对称，所以整体看起来很对称，这一点，不规则数独一般都做不到。

还有斜线数独也有很强的对称性。

这个数独看起来给的数也不少了，有27个，但是很难。

想了半天，一个都推不出来，还好我有下面的代码。

输入：

2..8..6.. .6..2..9. ..4..6..7 1..6..9.. .7..3..8. ..9..5..1 5..4..3.. .1..5..4. ..2..8..9

输出：

293817654 761524893 854396127 138642975 475931286 629785431 587469312 916253748 342178569

这就是这个数独的解了。

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入: [   ["5","3",".",".","7",".",".",".","."],   ["6",".",".","1","9","5",".",".","."],   [".","9","8",".",".",".",".","6","."],   ["8",".",".",".","6",".",".",".","3"],   ["4",".",".","8",".","3",".",".","1"],   ["7",".",".",".","2",".",".",".","6"],   [".","6",".",".",".",".","2","8","."],   [".",".",".","4","1","9",".",".","5"],   [".",".",".",".","8",".",".","7","9"] ] 输出: true 示例 2:

输入: [   ["8","3",".",".","7",".",".",".","."],   ["6",".",".","1","9","5",".",".","."],   [".","9","8",".",".",".",".","6","."],   ["8",".",".",".","6",".",".",".","3"],   ["4",".",".","8",".","3",".",".","1"],   ["7",".",".",".","2",".",".",".","6"],   [".","6",".",".",".",".","2","8","."],   [".",".",".","4","1","9",".",".","5"],   [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 说明:

一个有效的数独（部分已被填充）不一定是可解的。 只需要根据以上规则，验证已经填入的数字是否有效即可。 给定数独序列只包含数字 1-9 和字符 '.' 。 给定数独永远是 9x9 形式的。